package List;
class ListNode{
    public int val;
    public ListNode next;
    public ListNode(int val){
        this.val=val;
    }
}
public class MyLinkedList {
    public ListNode head;
    public void createList() {
        ListNode listNode1=new ListNode(12);
        ListNode listNode2=new ListNode(3);
        ListNode listNode3=new ListNode(5);
        ListNode listNode4=new ListNode(2);
        listNode1.next=listNode2;
        listNode2.next=listNode3;
        listNode3.next=listNode4;
        this.head=listNode1;
    }
    public void show() {
        ListNode cur=head;
        while (cur!=null){
            System.out.print(cur.val+" ");
            cur=cur.next;
        }
        System.out.println();
    }
    public int size() {
        ListNode cur=head;
        int count=0;
        while (cur!=null){
            count++;
            cur=cur.next;
        }
        return count;
    }
    public boolean contains(int val) {
        ListNode cur=head;
        if(cur==null){
            return false;
        }
        while (cur!=null){
            if(cur.val==val){
                return true;
            }
            cur=cur.next;
        }
        return false;
    }
    public void addFirst(int data) {
        ListNode listNode=new ListNode(data);
        if (this.head==null){
            this.head=listNode;
        }
        else{
            listNode.next=this.head;
            this.head=listNode;
        }
    }
    public void addLast(int data) {
        ListNode listNode=new ListNode(data);
        if (this.head==null){
            this.head=listNode;
        }
        else{
            ListNode cur=head;
            while (cur.next!=null){
                cur=cur.next;
            }
            cur.next=listNode;
        }
    }
    public ListNode searchPrev(int index) {
        ListNode cur=this.head;
        int count=0;
        while (count!=index-1){
            cur=cur.next;
            count++;
        }
        return cur;
    }
    public void addIndex(int index,int data){
        int count=0;
        if(index<0||index>size()){
            System.out.println("下标不合法");
            return;
        }
       if (index==0){
           addFirst(data);
           return;
       }
       if(index==size()){
           addLast(data);
           return;
       }
       ListNode cur=searchPrev(index);
       ListNode listNode=new ListNode(data);
       listNode.next=cur.next;
       cur.next=listNode;
       return;
    }
    public ListNode searchPrevNode(int val) {
        ListNode listNode=this.head;
        while (listNode.next!=null){
            if(listNode.next.val==val){
                return listNode;
            }
            listNode=listNode.next;
        }
        return null;
    }
    public void remove(int val) {
        if(this.head==null){
            return;
        }
        if(this.head.val==val){
            this.head=this.head.next;
        }
        ListNode cur=searchPrevNode(val);
        if(cur==null){
            System.out.println("没有删除的结点");
            return;
        }
        cur=cur.next.next;
    }
    public void removeAllKey(int val) {
        if(this.head==null){
            return;
        }
        ListNode cur=this.head.next;
        ListNode prev=this.head;
        while (cur!=null){
            if(cur.val==val){
                cur=cur.next;
            }
            else{
                prev.next=cur;
                cur=cur.next;
            }
        }
        if(this.head.val==val){
            this.head=this.head.next;
        }
    }
    public void clear(){
        while (this.head!=null){
            ListNode curNext = this.head.next;
            this.head.next = null;
            this.head = curNext;
        }
    }
    public ListNode reverseList() {
        if(this.head==null||this.head.next==null){
            return this.head;
        }
        ListNode n1=null;
        ListNode n2=this.head;
        ListNode n3=this.head.next;
        while (n2!=null){
            n2.next=n1;
            n1=n2;
            n2=n3;
            if(n3!=null){
                n3=n3.next;
            }
        }
        return n1;
    }
    public void show2(ListNode newHead) {
        ListNode cur = newHead;
        while(cur != null) {
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }
    public ListNode reverseList2() {
        ListNode cur = this.head;
        ListNode prev = null;
        ListNode newHead = null;
        while (cur != null) {
            ListNode curNext = cur.next;
            if(curNext == null) {
                newHead = cur;
            }
            cur.next = prev;
            prev = cur;
            cur = curNext;
        }
        return newHead;
    }
    public ListNode middleNode() {
        if(this.head==null){
            return null;
        }
        ListNode fast=this.head;
        ListNode slow=this.head;
        while (fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        return slow;
    }
    public ListNode findKthToTail(int k) {
        if(this.head==null){
            return null;
        }
        ListNode fast=this.head;
        ListNode slow=this.head;
        while (k-1!=0){
            k--;
            fast=fast.next;
        }
        while (fast.next!=null){
            fast=fast.next;
            slow=slow.next;
        }
        return slow;
    }
    public ListNode partition( int x) {
        if(this.head==null){
            return null;
        }
        ListNode cur=this.head;
        ListNode phead1=new ListNode(-1);
        ListNode phead2=new ListNode(1);
        ListNode n1=phead1;
        ListNode n2=phead2;
        while (cur!=null)
        {
            if(cur.val<x){
                n1.next=cur;
                n1=n1.next;
            }
            else {
                n2.next=cur;
                n2=n2.next;
            }
            cur=cur.next;
        }
        n1.next=n2;
        n2.next=null;
        return phead1.next;
    }
    public ListNode deleteDuplication() {
        if (this.head==null){
            return null;
        }
        ListNode phead=new ListNode(-1);
        ListNode n3=phead;
        phead.next=this.head;
        ListNode n1=phead;
        ListNode n2=phead.next;
        int tmp=-1;
        while(n2!=null){
            if(n1.val!=n2.val){
                if(n1.val!=tmp){
                    n3.next=n1;
                    n3=n3.next;
                }
            }
            if(n1.val==n2.val){
                tmp=n1.val;
            }
            if(n2.next==null){
                if(n2.val!=tmp){
                    n3.next=n2;
                    n3=n3.next;
                }
            }
            n1=n1.next;
            n2=n2.next;
        }
        n3.next=null;
        return phead.next;
    }
    public boolean chkPalindrome() {
        if(this.head==null||this.head.next==null){
            return true;
        }
        ListNode fast=this.head;
        ListNode slow=this.head;
        while (fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        ListNode cur=slow.next;
        while (cur.next!=null){
            ListNode curNext=cur.next;
            cur.next=slow;
            slow=cur;
            cur=curNext;
        }
        while (slow != head) {
            if(slow.val != head.val) {
                return false;
            }
            if(head.next == slow) {
                return true;
            }
            head = head.next;
            slow = slow.next;
        }
        return true;
    }
    public boolean hasCycle1() {
        if(this.head==null){
            return false;
        }
        ListNode fast=this.head;
        ListNode slow=this.head;
        while (fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow){
                return true;
            }
        }
        return false;
    }
    public void createCycle() {
        ListNode cur = this.head;
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = this.head.next;
    }
    public boolean hasCycle() {
        ListNode fast = this.head;
        ListNode slow = this.head;

        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if(slow == fast) {
                break;
            }
        }
        if(fast == null || fast.next == null) {
            return false;
        }
        return true;
    }
    public ListNode detectCycle() {
        ListNode fast = this.head;
        ListNode slow = this.head;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if(slow == fast) {
               ListNode n1=this.head;
                while (n1!=fast){
                    n1=n1.next;
                    fast=fast.next;
                }
                return fast;
            }
        }
        return null;
    }
}
